package com.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 78. 子集
 * 递归法实现子集枚举
 *
 * @author fy
 * @date 2022/4/29 10:28
 */
public class Solution78 {

    private List<List<Integer>> res;

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        res = new ArrayList<>();
        List<Integer> preList = new ArrayList<>();
        for (int count = 0; count <= n; count++) {
            dfs(nums, count, 0, preList);
        }
        return res;
    }

    private void dfs(int[] nums, int count, int index, List<Integer> preList) {
        if (count == 0) {
            res.add(new ArrayList<>(preList));
            return;
        }
        // 这里可以剪枝, 如果后续的长度不够凑出count个元素的话,
        // 就是i < nums.length - count + 1 的话, 这次循环可以不进行
        for (int i = index; i < nums.length - count + 1; i++) {
            preList.add(nums[i]);
            dfs(nums, count - 1, i + 1, preList);
            preList.remove(preList.size() - 1);
        }
    }

}
